﻿using System.Data;

namespace DataStructure;

public class BST<Key> : IBST<Key> where Key : IComparable<Key>
{
    private class Node
    {
        public Key key;
        public Node left;
        public Node right;

        public Node(Key key)
        {
            this.key = key;
            left = null;
            right = null;
        }
    }

    private  Node root;
    private int N;

    public BST()
    {
        root = null;
        N = 0;
    }

    public int Count { get { return N; } }

    public bool IsEmpty { get { return N == 0 || root == null; } }

    //往二叉查找树中添加元素，非递归实现，类似链表的尾插法添加。最好：O（log(n)），最差：O（n）
    public  bool add(Key key)
    {
        if (root == null)
        {
            root = new Node(key);
            N++;
            return true;
        }

        Node pre = null;
        Node cur = root;

        while (cur != null)
        {
            if (key.CompareTo(cur.key) == 0)
            {
                return false;
            }

            pre = cur;

            if (key.CompareTo(cur.key) < 0)
            {
                cur = cur.left;
            }
            else   //e.CompareTo(cur.e) > 0 
            {
                cur = cur.right;
            }
        }

        cur = new Node(key);

        if (key.CompareTo(pre.key) < 0)
        {
            pre.left = cur;
        }
        else    //e.CompareTo(pre.e) > 0
        {
            pre.right = cur;
        }

        N++;
        return true;
    }

    //往二叉查找树中添加元素，递归实现
    public  bool Add(Key key)
    {
        if (Contains(key))
        {
            return false;
        }

        root = Add(root, key);
        return true;
    }

    //以node为根的树中添加元素e，添加后返回根节点node。 最好：O（log(n)），最差：O（n）
    private  Node Add(Node node, Key key)
    {
        if (node == null) //初始条件
        {
            N++;
            return new Node(key);
        }

        if (key.CompareTo(node.key) < 0)
        {
            node.left = Add(node.left, key);
        }
        else if (key.CompareTo(node.key) > 0)
        {
            node.right = Add(node.right, key);
        }

        return node;
    }

    //查询二叉查找树是否包含元素e
    public  bool  Contains(Key key)
    {
        return Contains(root, key);
    }

    //以node为根的树是否包含元素e。最好：O（log(n)），最差：O（n）
    private  bool Contains(Node node, Key key)
    {
        if (node == null) //初始条件
        {
            return false;
        }

        if (key.CompareTo(node.key) == 0)
        {
            return true;
        }

        if (key.CompareTo(node.key) < 0)
        {
            return Contains(node.left, key);
        }

        //key.CompareTo(node.key) > 0
        return Contains(node.right, key);
    }

    // 二叉查找树的前序遍历
    public  void PreOrder()
    {
        PreOrder(root); 
    }

    // 前序遍历以node为根的二叉查找树
    private  void PreOrder(Node node)
    {
        if (node == null) //初始条件
        {
            return;
        }

        Console.WriteLine(node.key);
        PreOrder(node.left);
        PreOrder(node.right);
    }

    // 二叉查找树的中序遍历
    public  void InOrder()
    {
        InOrder(root);
    }

    //中序遍历以node为根的二叉查找树
    private  void InOrder(Node node)
    {
        if (node == null) //初始条件
        {
            return;
        }

        InOrder(node.left);
        Console.WriteLine(node.key);
        InOrder(node.right);
    }

    // 二叉查找树的后序遍历
    public  void PostOrder()
    {
        PostOrder(root);
    }

    // 后序遍历以node为根的二叉查找树
    private  void PostOrder(Node node)
    {
        if (node == null) //初始条件
        {
            return;
        }

        PostOrder(node.left);
        PostOrder(node.right);
        Console.WriteLine(node.key);
    }

    // 二叉查找树的层序遍历，BFS
    public  void LevelOrder()
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        while (q.Count != 0)
        {
            Node cur = q.Dequeue();
            Console.WriteLine(cur.key);

            if (cur.left != null)
                q.Enqueue(cur.left);

            if (cur.right != null)
                q.Enqueue(cur.right);
        }
    }

    // 寻找二叉查找树的最小元素
    public  Key Min()
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        return Min(root).key;
    }

    // 返回以node为根的二叉查找树的最小值所在的节点
    private  Node Min(Node node)
    {
        if (node.left == null)
        {
            return node;
        }

        return Min(node.left);
    }

    // 寻找二叉查找树的最大元素
    public  Key Max()
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        return Max(root).key;
    }

    // 返回以node为根的二叉查找树的最大值所在的节点
    private  Node Max(Node node)
    {
        if (node.right == null)
        {
            return node;
        }

        return Max(node.right);
    }

    // 从二叉查找树中删除最小值所在节点
    public  Key RemoveMin()
    {
        Key ret = Min();
        root = RemoveMin(root);
        return ret;
    }

    // 删除掉以node为根的二叉查找树中的最小节点
    // 返回删除节点后新的二叉查找树的根
    private  Node RemoveMin(Node node)
    {
        if (root == null)
        {
            return null;
        }

        if (node.left == null) //初始条件
        {
            N--;
            return node.right;
        }

        node.left = RemoveMin(node.left);
        return node;
    }

    // 从二叉查找树中删除最大值所在节点
    public  Key RemoveMax()
    {
        Key ret = Max();
        root = RemoveMax(root);
        return ret;
    }

    // 删除掉以node为根的二叉查找树中的最大节点
    // 返回删除节点后新的二叉查找树的根
    private  Node RemoveMax(Node node)
    {
        if (root == null)
        {
            return null;
        }

        if (node.right == null)
        {
            N--;
            return node.left;
        }

        node.right = RemoveMax(node.right);
        return node;
    }

    // 从二叉查找树中删除元素为key的节点
    public  bool Remove(Key key)
    {
        if (!Contains(key))
        {
            return false;
        }

        root = Remove(root, key);
        return true;
    }

    // 删除掉以node为根的二叉查找树中值为e的节点
    // 返回删除节点后新的二叉查找树的根
    private  Node Remove(Node node, Key key)
    {
        if (node == null) return null;

        if (key.CompareTo(node.key) < 0)
        {
            node.left = Remove(node.left, key);
            return node;
        }
        else if (key.CompareTo(node.key) > 0)
        {
            node.right = Remove(node.right, key);
            return node;
        }
        else //key.CompareTo(node.key) == 0
        {
            // 要删除的节点只有左孩子
            if (node.right == null)
            {
                N--;
                return node.left;
            }

            // 要删除的节点只有右孩子
            if (node.left == null)
            {
                N--;
                return node.right;
            }

            // 要删除的节点左右都有孩子
            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置

            Node s = Min(node.right);
            s.right = RemoveMin(node.right);
            s.left = node.left;

            return s;
        }
    }

    //二叉树的最大高度
    public  int MaxHeight()
    {
        return MaxHeight(root);
    }

    //计算以node为根的二叉树的最大高度
    private  int MaxHeight(Node node)
    {
        if (node == null) return 0;

        //int l = MaxHeight(node.left);
        //int r = MaxHeight(node.right);
        //return Math.Max(l, r) + 1;

        //选择左右子树中最高的那一颗子树在加上node本身的高度。得到以node为根二叉树的最大高度
        return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
    }

    //排名(从0起）。返回BST中小于key的键的数量
    public  int Rank(Key key)
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }
        return Rank(root, key);
    }

    private  int Rank(Node node, Key key)
    {
        if (node == null)
        {
            return 0;
        }

        if (key.CompareTo(node.key) <= 0)
        {
            return Rank(node.left, key);
        }

        return 1 + Rank(node.left, key) + Rank(node.right, key);
    }

    //找出排名为k(从0起)的键
    public  Key Select(int k)
    {
        if (k < 0 || k >= N)
        {
            throw new IndexOutOfRangeException("索引越界");
        }

        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        return Select(root, k).key;
    }

    private  Node Select(Node node, int k)
    {
        if (node == null)
        {
            return null;
        }

        int rank = Rank(node.key);

        if (rank == k)
        {
            return node;
        }

        if (rank > k)
        {
            return Select(node.left, k);
        }

        return Select(node.right, k);
    }

    //找出小于或等于key的最大键
    public  Key Floor(Key key)
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        Node node = Floor(root, Rank(key));
        if (node == null)
        {
            new InvalidOperationException("这样的节点不存在！");
        }

        return node.key;
    }

    private  Node Floor(Node node, int k)
    {
        if (node == null)
        {
            return null;
        }

        int rank = Rank(node.key);

        if (rank == k || rank + 1 == k)
        {
            return node;
        }

        if (rank < k)
        {
            return Floor(node.right, k);
        }

        return Floor(node.left, k);
    }

    //找出大于或等于key的最小键
    public  Key Ceiling(Key key)
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        Node node = Ceiling(root, Rank(key));
        if (node == null)
        {
            new InvalidOperationException("这样的节点不存在！");
        }

        return node.key;
    }

    private  Node Ceiling(Node node, int k)
    {
        if (node == null)
        {
            return null;
        }

        int rank = Rank(node.key);

        if (rank == k || rank - 1 == k)
        {
            return node;
        }

        if (rank < k)
        {
            return Floor(node.right, k);
        }

        return Floor(node.left, k);
    }
}

public class BST<Key, Value> : IBST<Key, Value> where Key : IComparable<Key>
{
    protected class Node
    {
        public Key key;
        public Value value;
        public Node left;
        public Node right;

        public Node(Key key, Value value)
        {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int N;

    public BST() 
    {
        root = null;
        N=0;
    }

    public int Count { get { return N; } }

    public bool IsEmpty { get { return N == 0 || root == null; } }

    public bool Add(Key key)
    {
        return false;
    }

    public void Add(Key key, Value value)
    {
        root = Add(root, key, value);
    }

    private Node Add(Node node, Key key, Value value)
    {
        if (node == null)
        {
            N++;            
            return new Node(key, value);
        }

        if (key.CompareTo(node.key) < 0)
        {
            node.left = Add((Node)node.left, key, value);
        }
        else if (key.CompareTo(node.key) > 0)
        {
            node.right = Add((Node)node.right, key, value);
        }
        else
        {
            node.value = value;
        }

        return node;
    }

    // 寻找二叉查找树的最小元素
    public Key Min()
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        return Min(root).key;
    }

    // 返回以node为根的二叉查找树的最小值所在的节点
    private Node Min(Node node)
    {
        if (node.left == null)
        {
            return node;
        }

        return Min(node.left);
    }

    public Key Max()
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        return Max(root).key;
    }

    private Node Max(Node node)
    {
        if (node == null)
        {
            return null;
        }

        if (node.right == null)
        {
            return node;
        }

        return Max(node.right);
    }

    public Key RemoveMin()
    {
        Key ret = Min();
        root = RemoveMin(root);
        return ret;
    }

    private Node RemoveMin(Node node)
    {
        if (node == null)
        {
            return null;
        }

        if (node.left == null)
        {
            N--;
            return node.right;
        }

        node.left = RemoveMin(node.left);
        return node;
    }

    // 从二叉查找树中删除最大值所在节点
    public Key RemoveMax()
    {
        Key ret = Max();
        root = RemoveMax(root);
        return ret;
    }

    // 删除掉以node为根的二叉查找树中的最大节点
    // 返回删除节点后新的二叉查找树的根
    private Node RemoveMax(Node node)
    {
        if (root == null)
        {
            return null;
        }

        if (node.right == null)
        {
            N--;
            return node.left;
        }

        node.right = RemoveMax(node.right);
        return node;
    }

    public bool Remove(Key key)
    {
        if (!Contains(key))
        {
            return false;
        }

        root = Remove(root, key);
        return true;
    }

    private Node Remove(Node node, Key key)
    {
        if (node == null)
        {
            return null;
        }

        if (key.CompareTo(node.key) < 0)
        {
            node.left = Remove(node.left, key);
            return node;
        }
        else if (key.CompareTo(node.key) > 0)
        {
            node.right = Remove(node.right, key);
            return node;
        }
        else //e.CompareTo(node.e) == 0
        {
            // 要删除的节点只有左孩子
            if (node.right == null)
            {
                N--;
                return node.left;
            }

            // 要删除的节点只有右孩子
            if (node.left == null)
            {
                N--;
                return node.right;
            }

            // 要删除的节点左右都有孩子
            Node s = Min(node.right);
            s.right = RemoveMin(node.right);
            s.left = node.left;

            return s;
        }
    }

    // 二叉查找树的前序遍历
    public void PreOrder()
    {
        PreOrder(root);
    }

    // 前序遍历以node为根的二叉查找树
    private void PreOrder(Node node)
    {
        if (node == null) //初始条件
        {
            return;
        }

        Console.WriteLine(node.key);
        PreOrder(node.left);
        PreOrder(node.right);
    }

    // 二叉查找树的中序遍历
    public void InOrder()
    {
        InOrder(root);
    }

    //中序遍历以node为根的二叉查找树
    private void InOrder(Node node)
    {
        if (node == null) //初始条件
        {
            return;
        }

        InOrder(node.left);
        Console.WriteLine(node.key);
        InOrder(node.right);
    }

    // 二叉查找树的后序遍历
    public void PostOrder()
    {
        PostOrder(root);
    }

    // 后序遍历以node为根的二叉查找树
    private void PostOrder(Node node)
    {

        if (node == null) //初始条件
        {
            return;
        }

        PostOrder(node.left);
        PostOrder(node.right);
        Console.WriteLine(node.key);
    }

    // 二叉查找树的层序遍历，BFS
    public void LevelOrder()
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        while (q.Count != 0)
        {
            Node cur = q.Dequeue();
            Console.WriteLine(cur.key);

            if (cur.left != null)
                q.Enqueue(cur.left);

            if (cur.right != null)
                q.Enqueue(cur.right);
        }
    }

    //返回以node为根节点的二叉查找树中，key所在的节点
    private Node GetNode(Node node, Key key)
    {
        if (node == null)
        {
            return null;
        }

        if (key.Equals(node.key))
        {
            return node;
        }

        if (key.CompareTo(node.key) < 0)
        {
            return GetNode(node.left, key);
        }

        //key.CompareTo(node.key) > 0
        return GetNode(node.right, key);
    }

    public bool Contains(Key key)
    {
        return GetNode(root, key) != null;
    }

    public Value Get(Key key)
    {
        Node node = GetNode(root, key);

        if (node == null)
        {
            throw new KeyNotFoundException("键" + key + "不存在，无法获取对应值");
        }
        else
        {
            return node.value;
        }
    }

    public void Set(Key key, Value newValue)
    {
        Node node = GetNode(root, key);

        if (node == null)
        {
            throw new KeyNotFoundException("键" + key + "不存在，无法更改对应值");
        }
        else
        {
            node.value = newValue;
        }
    }

    public int MaxHeight()
    {
        return MaxHeight(root);

    }

    private int MaxHeight(Node node)
    {
        if (node == null) return 0;

        //int l = MaxHeight(node.left);
        //int r = MaxHeight(node.right);
        //return Math.Max(l, r) + 1;

        //选择左右子树中最高的那一颗子树在加上node本身的高度。得到以node为根二叉树的最大高度
        return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
    }

    //排名(从0起）。返回BST中小于key的键的数量
    public int Rank(Key key)
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }
        return Rank(root, key);
    }

    private int Rank(Node node, Key key)
    {
        if (node == null)
        {
            return 0;
        }

        if (key.CompareTo(node.key) <= 0)
        {
            return Rank(node.left, key);
        }

        return 1 + Rank(node.left, key) + Rank(node.right, key);
    }

    public Key Select(int k)
    {
        if (k < 0 || k >= N)
        {
            throw new IndexOutOfRangeException("索引越界");
        }

        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        return Select(root, k).key;
    }

    private Node Select(Node node, int k)
    {
        if (node == null)
        {
            return null;
        }

        int rank = Rank(node.key);

        if (rank == k)
        {
            return node;
        }

        if (rank > k)
        {
            return Select(node.left, k);
        }

        return Select(node.right, k);
    }

    //找出小于或等于key的最大键
    public Key Floor(Key key)
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        Node node = Floor(root, Rank(key));
        if (node == null)
        {
            new InvalidOperationException("这样的节点不存在！");
        }

        return node.key;
    }

    private Node Floor(Node node, int k)
    {
        if (node == null)
        {
            return null;
        }

        int rank = Rank(node.key);

        if (rank == k || rank + 1 == k)
        {
            return node;
        }

        if (rank < k)
        {
            return Floor(node.right, k);
        }

        return Floor(node.left, k);
    }

    //找出大于或等于key的最小键
    public Key Ceiling(Key key)
    {
        if (root == null)
        {
            throw new InvalidOperationException("空树！");
        }

        Node node = Ceiling(root, Rank(key));
        if (node == null)
        {
            new InvalidOperationException("这样的节点不存在！");
        }

        return node.key;
    }

    private Node Ceiling(Node node, int k)
    {
        if (node == null)
        {
            return null;
        }

        int rank = Rank(node.key);

        if (rank == k || rank - 1 == k)
        {
            return node;
        }

        if (rank < k)
        {
            return Floor(node.right, k);
        }

        return Floor(node.left, k);
    }
}